package Fibonacci;

import java.util.Arrays;

//优化记忆法
public class Fibonacci {
    public static void main(String[] args) {
        combination(8);
        combination(7);
        combination(6);
        combination(5);
        combination(4);
        combination(3);
        combination(2);
        combination(1);
    }

    public static int fun (int n, int[] arr) {
        if (arr[n] != -1) {
            return arr[n];
        }

        int x = fun(n-1,arr);
        int y = fun(n-2,arr);
        arr[n] = x+y;
        return arr[n];
    }

    public static int[] list (int m) {
        int[] arr = new int[ m + 1];
        Arrays.fill(arr,-1);
        arr[0] = 0;
        arr[1] = 1;
        return arr;
    }

    public static void combination(int n) {
        int[] arr = list(n);
        System.out.println(fun(n, arr));

    }
}
